package problemLCR159;

class Solution {
    public int[] inventoryManagement(int[] stock, int cnt) {
        if(cnt == 0) return new int[]{};
        //1.建大小为cnt的大根堆
        int n = stock.length;
        int[] heap = new int[cnt];
        for(int i = 0; i<cnt; i++) {
            heap[i] = stock[i];
        }
        creatHeap(heap);

        for(int i = cnt; i<n; i++) {
            if(stock[i] < heap[0]) {
                heap[0] = stock[i];
                adjustDown(heap, 0, heap.length);
            }
        }

        return heap;
    }
    public void creatHeap(int[] heap) {
        int cur = (heap.length - 1 -1)/2;
        while(cur >= 0) {
            adjustDown(heap, cur, heap.length);
            cur--;
        }
    }
    public void adjustDown(int[] heap, int parent, int end) {
        int child = parent*2+1;
        while(child < end) {
            if(child+1 < end && heap[child+1] > heap[child]) {
                child++;
            }
            if(heap[parent] < heap[child]) {
                swap(heap, child, parent);
                parent = child;
                child = parent*2+1;
            }else {
                break;
            }
        }

    }
    public void swap(int[] arr, int a, int b) {
        int t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }
}